This invention relates to packet communications in a radio-based mesh communications network. In particular, the present invention is an optimization of the apparatus utilized at nodes that link the mesh radio network with a relatively high capacity communication link.
Packet communications is a form of data communication whereby segments or packets of data are routed with error checking and confirmation of receipt. Packets may be transmitted directly between a source node and a destination node or may be relayed via a number of relay nodes. Several methods of data packet routing are known.
A radio-based mesh network comprises radio nodes interconnected by a mesh of radio links. Collectively, the nodes collect, route, and deliver data packets. U.S. Pat. No. 5,488,608, teaches a method of routing packets in a heavily interconnected mesh network. According to the method described therein, each node in a network is uniquely identified by an absolute coordinate-based address, and packet routing decisions are made at each node. When a node receives a packet, the node chooses a desired forwarding route by examining the ultimate destination coordinates of the packet and the node coordinates of its neighboring nodes. The node then sends a poll to the most advantageous neighboring node to determine if it is available to receive the packet. When the node has determined that a neighboring node is available, the node forwards the packet to the selected neighboring node. Finally, the node stores the packet's destination address and the selected neighboring node's address in a routing table. The routing table provides a quick and efficient means for choosing a forwarding node the next time the node receives a packet bound for the same destination.
In a mesh network, access points are included at which the radio-based network interfaces with a relatively high speed communications link, such as a wireline. These access points permit packet communication between the mesh network and other networks linked by the wireline. Additionally, packets bound for a distant portion of the mesh network are generally routed over the wireline because the wired link provides much higher speed and capacity than the radio-based mesh network and therefore increases the overall performance of the network. Thus, the network generally seeks to route packets to an access point as soon as possible. These access points must provide a higher capacity than other nodes in the network in order to prevent bottlenecking.
In previous embodiments of radio-based mesh packet networks, a wire access point (WAP) comprises a plurality of radios that permit simultaneous access to a wireline by a plurality of nodes. Additionally, the plurality of WAP radios provide a plurality of alternate routes to and from the wireline. Nodes (clients) seeking to transmit a packet to a WAP maintain a local routing list of the WAP radios as possible recipients of the data packet. When a client wishes to transmit a packet to the WAP, the client polls the WAP radios on its routing list and sends the data packet payload to one of the WAP radios that responds. The other WAP radios remain free to service other clients.
While prior art WAPs with multiple radios provide relatively high capacity for access to the wired backbone, they exhibit several drawbacks. First, because each WAP radio must be separately polled, a relatively high number of polls is directed at the WAP. This results in increased destructive packet collisions, especially when traffic to the WAP is heavy. These destructive packet collisions cause increased latency at times of heavy traffic when greater throughput is needed. Second, employing multiple radios in the WAP decreases overall efficiency. For instance, clients that access the WAP must create and maintain a routing list of the multiple WAP radios. Also, clients must send multiple polls and process multiple poll responses before data exchange with the WAP can occur.
Methods are known in the prior art for optimizing the allocation of resources among a plurality of clients. For example, U.S. Pat. No. 5,371,780 teaches a method and apparatus for allocating cellular resources among multiple clients by assigning priorities to the clients and then iteratively allocating available resources to the highest priority clients. U.S. Pat. No. 5,530,693 teaches a method and apparatus for handing off a client in the middle of the transmission of a data packet from a first cell site to a second cell site. If the first cell has already transmitted a portion of the packet to the client, the client notifies the second cell and the second cell then transmits only that portion of the packet that the client has not yet received. This eliminates the need to resend the entire packet.
However, the prior art does not address the problems caused by and associated with the polling of a plurality of radios at an access point.